0567. 字符串的排列【中等】

• 1. 📝 题目描述
• 2. 🎯 s.1 - 滑动窗口

1. 📝 题目描述

• leetcode

给你两个字符串 s1 和 s2，写一个函数来判断 s2 是否包含 s1 的 排列。如果是，返回 true ；否则，返回 false。

排列是字符串中所有字符的重新排序。

换句话说，s1 的排列之一是 s2 的 子串。

---

示例 1：

输入：s1 = "ab" s2 = "eidbaooo"
输出：true
解释：s2 包含 s1 的排列之一 ("ba").

示例 2：

输入：s1= "ab" s2 = "eidboaoo"
输出：false

---

提示：

• 1 <= s1.length, s2.length <= 10^4
• s1 和 s2 仅包含小写字母

2. 🎯 s.1 - 滑动窗口

c

bool checkInclusion(char* s1, char* s2) {
    int len1 = strlen(s1), len2 = strlen(s2);
    if (len1 > len2) return false;
    int cnt[26] = {0};
    for (int i = 0; i < len1; i++) {
        cnt[s1[i] - 'a']++;
        cnt[s2[i] - 'a']--;
    }
    int diff = 0;
    for (int i = 0; i < 26; i++) if (cnt[i] != 0) diff++;
    if (diff == 0) return true;
    for (int i = len1; i < len2; i++) {
        int r = s2[i] - 'a', l = s2[i - len1] - 'a';
        if (cnt[r] == 0) diff++;
        cnt[r]--;
        if (cnt[r] == 0) diff--;
        if (cnt[l] == 0) diff++;
        cnt[l]++;
        if (cnt[l] == 0) diff--;
        if (diff == 0) return true;
    }
    return false;
}

js

/**
 * @param {string} s1
 * @param {string} s2
 * @return {boolean}
 */
var checkInclusion = function (s1, s2) {
  if (s1.length > s2.length) return false
  const cnt = new Array(26).fill(0)
  for (let i = 0; i < s1.length; i++) {
    cnt[s1.charCodeAt(i) - 97]++
    cnt[s2.charCodeAt(i) - 97]--
  }
  if (cnt.every((v) => v === 0)) return true
  for (let i = s1.length; i < s2.length; i++) {
    cnt[s2.charCodeAt(i) - 97]--
    cnt[s2.charCodeAt(i - s1.length) - 97]++
    if (cnt.every((v) => v === 0)) return true
  }
  return false
}

py

class Solution:
    def checkInclusion(self, s1: str, s2: str) -> bool:
        if len(s1) > len(s2):
            return False
        cnt = [0] * 26
        for i in range(len(s1)):
            cnt[ord(s1[i]) - 97] += 1
            cnt[ord(s2[i]) - 97] -= 1
        if all(v == 0 for v in cnt):
            return True
        for i in range(len(s1), len(s2)):
            cnt[ord(s2[i]) - 97] -= 1
            cnt[ord(s2[i - len(s1)]) - 97] += 1
            if all(v == 0 for v in cnt):
                return True
        return False

• 时间复杂度：$O(n+m)$，其中 n 和 m 分别是 s1 和 s2 的长度
• 空间复杂度：$O(1)$，只使用固定大小为 26 的数组

算法思路：

• 维护一个长度为 len(s1) 的滑动窗口和字符频次差值数组
• 窗口每次右移一位，更新进出字符的频次差
• 当所有差值为 0 时说明窗口内是 s1 的一个排列